package leetcode.heap.offer.p40;

/**
 * 
 * @Title: Solution40.java 
 * @Package leetcode.offer.p40 
 * @Description: 剑指 Offer 40. 最小的k个数
 *                  使用自定义的基于最大堆的优先级队列
 * @author CandyWall   
 * @date 2021年1月9日 上午11:02:34 
 * @version V1.0
 */
public class Solution40_v1 {
    public class CandyArray<E> {
        private E[] data;
        private int size;
        
        public CandyArray() {
            this(10);
        }
        
        /**
         * 传入数组的容量初始化Array
         * @param capacity
         */
        public CandyArray(int capacity) {
            data = (E[]) new Object[capacity];
            size = 0;
        }
        
        public CandyArray(E[] arr) {
            data = (E[]) new Object[arr.length];
            System.arraycopy(arr, 0, data, 0, arr.length);
            /*for(int i = 0; i < arr.length; i++) {
                data[i] = arr[i];
            }*/
            size = arr.length;
        }

        /**
         * 获取数组中的元素个数
         * @return
         */
        public int getSize() {
            return size;
        }
        
        /**
         * 获取数组的容量
         * @return
         */
        public int getCapacity() {
            return data.length;
        }
        
        /**
         * 判断数组是否为空
         * @return
         */
        public boolean isEmpty() {
            return size == 0;
        }
        
        /**
         * 校验待操作的数组下标是否合法
         */
        private void checkArrayIndexRange(int index) {
            if(index > size || index < 0) {
                throw new IllegalArgumentException("索引index不合法！");
            }
        }
        
        /**
         * 在数组末尾添加一个元素
         * @param e
         */
        public void addLast(E e) {
            add(size, e);
        }
        
        /**
         * 在数组开头添加一个元素
         * @param e
         */
        public void addFirst(E e) {
            add(0, e);
        }
        
        /**
         * 在第index个位置插入新元素
         * @param index
         * @param e
         */
        public void add(int index, E e) {
            checkArrayIndexRange(index);

            if(size == data.length) {
                resize(data.length << 1);
            }
            
            //下标大于等于index的元素均后移一个单位
            for(int i = size; i > index; i--) {
                data[i] = data[i - 1];
            }
            
            data[index] = e;
            size++;
        }
        
        /**
         * 数组扩容
         */
        private void resize(int capacity) {
            E[] newArray = (E[]) new Object[capacity];
            System.arraycopy(data, 0, newArray, 0, size);
            data = newArray;
        }
        
        /**
         * 获取index索引位置的元素
         * @param index
         * @return
         */
        public E get(int index) {
            checkArrayIndexRange(index);
            
            return data[index];
        }
        
        /**
         * 获取数组中的第一个元素
         * @return 
         */
        public E getFirst() {
            return get(0);
        }
        
        /**
         * 获取数组中的最后一个元素
         * @return 
         */
        public E getLast() {
            return get(size - 1);
        }
        
        /**
         * 将index索引出的值改成e
         * @param index
         * @param e
         */
        public void set(int index, E e) {
            checkArrayIndexRange(index);
            
            data[index] = e;
        }
        
        /**
         * 查找数组是否有元素e
         * @param e
         */
        public boolean contains(E e) {
            for(int i = 0; i < size; i++) {
                if(data[i].equals(e)) {
                    return true;
                }
            }
            return false;
        }
        
        /**
         * 查找数组中元素e所在的索引，如果不存在就返回-1
         * @param e
         * @return
         */
        public int find(E e) {
            for(int i = 0; i < size; i++) {
                if(data[i].equals(e)) {
                    return i;
                }
            }
            return -1;
        }
        
        /**
         * 从数组中删除index位置的元素，并返回删除的元素
         * @return
         */
        public E remove(int index) {
            checkArrayIndexRange(index);
            E ret = data[index];
            // 后面的元素往前挪填补空缺
            for(int i = index; i < size - 1; i++) {
                data[i] = data[i + 1];
            }
            size--;
            data[size] = null;
            
            // 如果数组中存放的元素是原来的四分之一，容量就减半
            if(size == data.length / 4 && (data.length >> 1) != 0) {
                resize(data.length >> 1);
            }
            return ret;
        }
        
        /**
         * 从数组中删除第一个元素，并返回删除的元素
         * @return
         */
        public E removeFirst() {
            return remove(0);
        }
        
        /**
         * 从数组中删除最后一个元素，并返回删除的元素
         * @return
         */
        public E removeLast() {
            return remove(size - 1);
        }
        
        /**
         * 从数组中删除元素e
         * @param e
         */
        public void removeElement(E e) {
            int index = find(e);
            if(index != -1) {
                remove(index);
            }
        }

        // 交换数组中两个位置的元素
        public void swap(int i, int j) {
            checkArrayIndexRange(i);
            checkArrayIndexRange(j);
            E temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }
    
    public class CandyMaxHeap<E extends Comparable<E>> {
        private CandyArray<E> data;
        
        public CandyMaxHeap(int capacity) {
            data = new CandyArray(capacity);
        }
        
        public CandyMaxHeap() {
            data = new CandyArray();
        }
        
        // 传入一个数组，将数组调整成一个最大堆
        public CandyMaxHeap(E[] arr) {
            data = new CandyArray(arr);
            for(int i = getParentIndex(data.getSize()); i >= 0; i--) {
                shiftDown(i);
            }
        }
        
        // 返回堆中的元素个数
        public int getSize() {
            return data.getSize();
        }
        
        // 堆是否为空
        public boolean isEmpty() {
            return data.isEmpty();
        }
        
        // 在完全二叉树的数组表示中，根据子节点的索引获取父节点的索引
        private int getParentIndex(int childIndex) {
            if(childIndex == 0) {
                throw new IllegalArgumentException("根节点是没有父节点的");
            }
            return (childIndex - 1) / 2;
        }
        
        // 在完全二叉树的数组表示中，根据父节点的索引获取左孩子节点的索引
        private int getLeftChildIndex(int parentIndex) {
            return parentIndex * 2 + 1;
        }
        
        // 在完全二叉树的数组表示中，根据父节点的索引获取右孩子节点的索引
        private int getRightChildIndex(int parentIndex) {
            return parentIndex *2 + 2;
        }
        
        public void add(E e) {
            data.addLast(e);
            shiftUp(data.getSize() - 1);
        }
        
        // 根据新加入的元素，向上调整堆
        private void shiftUp(int childIndex) {
            while(childIndex > 0 && data.get(getParentIndex(childIndex)).compareTo(data.get(childIndex)) < 0) {
                data.swap(getParentIndex(childIndex), childIndex);
                childIndex = getParentIndex(childIndex);
            }
        }
        
        // 获取堆中最大元素，即堆顶元素
        public E getMax() {
            if(data.getSize() == 0) {
                throw new IllegalArgumentException("堆为空，没有元素！");
            }
            return data.get(0);
        }
        
        // 提取堆中最大元素，并将最大元素从堆中移除
        public E extractMax() {
            // 获取堆中最大元素
            E ret = getMax();
            
            // 将最大元素从堆中删除
            // 这里采用堆中最后一个元素和堆顶元素交换，并且删除最后一个元素的方式完成删除
            // data.set(0, data.remove(data.getSize() - 1));
            data.swap(0, data.getSize() - 1);
            data.removeLast();
            shiftDown(0);
            
            return ret;
        }

        public int getCapacity() {
            return data.getCapacity();
        }

        // 根据堆顶的新元素，向下调整堆
        private void shiftDown(int parentIndex) {
            // 左孩子的索引越界，那么表示没有孩子节点了，调整操作结束
            // 反之继续调整堆
            while(getLeftChildIndex(parentIndex) < data.getSize()) {
                // 获取左孩子的索引
                int j = getLeftChildIndex(parentIndex);
                // 如果有右孩子，并且右孩子的值更大，记录右孩子的索引
                if(j + 1 < data.getSize() && data.get(j).compareTo(data.get(j + 1)) < 0) {
                    j++;
                }
                // data.get(j) 是 左右孩子中的较大者
                // 如果父节点大于等于子节点，没有违反最大堆的规则，停止调整
                if(data.get(parentIndex).compareTo(data.get(j)) >= 0) {
                    break;
                } 
                
                // 如果父节点比子节点小，交换父子节点的值
                data.swap(parentIndex, j);
                parentIndex = j;
            }
        }
        
        // 取出堆中最大的元素，并且替换成元素e
        public E replace(E e) {
            E ret = getMax();
            data.set(0, e);
            return ret;
        }
    }
    
    public interface CandyQueue<E> {
        int getSize();
        
        boolean isEmpty();
        
        void enqueue(E e);
        
        E dequeue();
        
        E getFront();

        int getCapacity();
    }
    
    public class CandyPriorityQueue<E extends Comparable<E>> implements CandyQueue<E> {
        private CandyMaxHeap<E> maxHeap;
        
        public CandyPriorityQueue() {
            maxHeap = new CandyMaxHeap();
        }

        @Override
        public int getSize() {
            return maxHeap.getSize();
        }

        @Override
        public boolean isEmpty() {
            return maxHeap.isEmpty();
        }

        @Override
        public void enqueue(E e) {
            maxHeap.add(e);
        }

        @Override
        public E dequeue() {
            return maxHeap.extractMax();
        }

        @Override
        public E getFront() {
            return maxHeap.getMax();
        }

        @Override
        public int getCapacity() {
            return maxHeap.getCapacity();
        }
    }
    
    public int[] getLeastNumbers(int[] arr, int k) {
        CandyPriorityQueue<Integer> queue = new CandyPriorityQueue<>();
        for(int i = 0; i < k; i++) {
            queue.enqueue(arr[i]);
        }
        for(int i = k; i < arr.length; i++) {
            if(!queue.isEmpty() && arr[i] < queue.getFront()) {
                queue.dequeue();
                queue.enqueue(arr[i]);
            }
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = queue.dequeue();
        }
        return res;
    }
}
